package domain.tc;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class CompTC {

	private Stack<VerTeX> ns = new Stack<VerTeX>();
	private Stack<SCC> cs = new Stack<SCC>();
	private Set<VerTeX> visited = new HashSet<VerTeX>();
	private List<VerTeX> entered = new ArrayList<VerTeX>();
//	private static Map<String, VerTeX> vertices = new HashMap<String, VerTeX>();

//	public static void main(String[] args) {
//		CompTC tc = new CompTC();
//		tc.setVerTex(7);
//		tc.setEdges(1, new int[] { 2 });
//		tc.setEdges(2, new int[] { 4, 3 });
//		tc.setEdges(3, new int[] { 2, 5 });
//		tc.setEdges(4, new int[] { 1, 3 });
//		tc.setEdges(5, new int[] { 6 });
//		tc.setEdges(6, new int[] { 5 });
//		tc.setEdges(7, new int[] { 6 });
//		tc.computeTransitiveClosure(tc.getVertex(2));
//		// tc.computeTransitiveClosure(tc.getVertex(7));
//		// System.err.println(tc.getVertex(2).toString()+": "+tc.getVertex(2).scc.component.toString());
//		System.err.println(tc.getVertex(6).toString() + ": "
//				+ tc.getVertex(4).scc.component.toString());
//		System.err.println("visited: " + tc.visited);
//	}

//	private void setEdges(int i, int[] js) {
//		VerTeX v = vertices.get("V" + i);
//		for (int j : js) {
//			String name = "V" + j;
//			VerTeX w = vertices.get(name);
//			if (w == null) {
//				System.err.println("Null vertex speicified: " + name);
//				return;
//			}
//			v.edges.add(w);
//		}
//	}

	public void setEdges(VerTeX v, Set<VerTeX> vs) {
		for (VerTeX w : vs) {
			v.edges.add(w);
		}
	}

//	private VerTeX getVertex(int j) {
//		String name = "V" + j;
//		if (vertices.containsKey(name)) {
//			return vertices.get(name);
//		} else {
//			VerTeX nv = new VerTeX(name);
//			vertices.put(name, nv);
//			return nv;
//		}
//	}

//	private Set<VerTeX> setVerTex(int i) {
//		Set<VerTeX> vs = new HashSet<VerTeX>();
//		for (int j = 1; j <= i; j++) {
//			vs.add(this.getVertex(j));
//		}
//		return vs;
//	}

	public void computeTransitiveClosure(VerTeX v) {
		// System.out.println("Computing "+v.toString());
		visited.add(v);
		// preserve entry order
		if (!entered.contains(v)) {
			entered.add(v);
		}
		v.root = v;
		v.scc = null;
		ns.push(v);
		v.selfloop = false;
		v.hsaved = cs.size();
		for (VerTeX w : v.edges) {
			if (w.equals(v)) {
				v.selfloop = true;
			} else {
				if (!this.visited.contains(w)) {
					computeTransitiveClosure(w);
				}
				if (w.scc == null) {
					// root v = min entry order of root v and root w
					if (entered.indexOf(w.root) < entered.indexOf(v.root)) {
						v.root = w.root;
						// System.out.println("entered: "+this.entered.toString());
					} else {
						v.root = v.root;
					}
				} else {
					// w has non-empty component
					List<VerTeX> dfs = DFS(v, new ArrayList<VerTeX>());
					System.out.println("DFS traversal of " + v.toString()
							+ ": " + dfs.toString());
					if (v.edges.contains(w) || (!dfs.contains(w))) {
						// not a forward edge v,w, meaning w is not a far
						// descendant of v or is a direct descendant of v.
						// System.out.println("push: "+w +" for node "+v);
						cs.push(w.scc);
					}
				}
			}
		}
		// build
		if (v.root.equals(v)) {
			SCC C = new SCC();
			if (ns.peek().equals(v)) {
				C.successors.clear();
			} else {
				C.successors.clear();
				C.successors.add(C);
			}
			// topological sorts of over components

			//
			while (cs.size() != v.hsaved) {
				SCC X = cs.pop();
				if (!C.successors.contains(X)) {
					C.successors.add(X);
					C.successors.addAll(X.successors);
				}
			}// end of while
			VerTeX w = null;
			while (w == null || !w.equals(v)) {
				w = ns.pop();
				w.scc = C;
				C.component.add(w);
			}
		}
	}

	// get all the successors of a given root
	public List<VerTeX> DFS(VerTeX root, List<VerTeX> given) {
		given.add(root);
		for (VerTeX v : root.edges) {
			if (!given.contains(v)) {
				given = DFS(v, given);
			}
		}
		return given;
	}

	class VerTeX {
		boolean selfloop = false;
		private String name;

		// Set<List<VerTeX>> successors = new HashSet<List<VerTeX>>();

		public VerTeX(String name) {
			this.name = name;
		}

		public String toString() {
			return this.name;
		}

		public VerTeX root = null;
		int hsaved = 0;
		public SCC scc = null;
		public Set<VerTeX> edges = new HashSet<VerTeX>();
	}

	class SCC {
		public List<VerTeX> component = new ArrayList<VerTeX>();
		public Set<SCC> successors = new HashSet<SCC>();
		public int sort = -1;
	}

	// sort the SCC's into a topological order, using their root entry order,
	// and remove duplicates
	public List<SCC> topologicalSortSCC(List<SCC> ins, List<VerTeX> entered) {
		Map<VerTeX, SCC> ts = new HashMap<VerTeX, SCC>();
		List<VerTeX> start = new ArrayList<VerTeX>();
		List<SCC> ret = new ArrayList<SCC>();
		for (SCC c : ins) {
			VerTeX root = c.component.get(0);
			// remove duplicates
			if (!ts.containsKey(root)) {
				c.sort = entered.indexOf(root);// get sort of the component
				ts.put(root, c);
				// if no outgoing edges from this root, it is a start node
				if (Collections.disjoint(root.edges, ts.keySet())) {
					start.add(root);
				}
			}
		}
		// use DFS to sort
		List<VerTeX> rv = new ArrayList<VerTeX>();
		Set<VerTeX> visited = new HashSet<VerTeX>();
		for (VerTeX v : start) {
			rv = this.visits(v, visited, ts.keySet(), rv);
		}
		for (int i = 0; i < rv.size(); i++) {
			ret.add(i, ts.get(rv.get(i)));
		}
		return ret;
	}

	private List<VerTeX> visits(VerTeX v, Set<VerTeX> visited, Set<VerTeX> all,
			List<VerTeX> ret) {
		if (!visited.contains(v)) {
			visited.add(v);
			for (VerTeX w : all) {
				if (v.edges.contains(w)) {
					this.visits(w, visited, all, ret);
				}
			}
			ret.add(v);
		}
		return ret;
	}

}
